import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
// https://leetcode.cn/problems/top-k-frequent-elements/
public class Topk {
        private static class PII{
            int num;
            int count;
            public PII(int num , int count ){
                this.num = num;
                this.count = count;
            }
        }
        public int[] topKFrequent(int[] nums, int k) {
            PriorityQueue<PII> queue = new PriorityQueue<PII>((t1, t2)->{
                return t2.count-t1.count;
            }
            );

            Arrays.sort(nums);
            ArrayList<PII> list = new ArrayList<>();
            int oldval = nums[0];
            PII p  = new PII(oldval,1);
            for(int i = 1 ; i < nums.length ; i ++)
            {
                if(nums[i] == oldval)
                {
                    p.count ++;
                }else
                {
                    queue.add(p);
                    p = new PII(nums[i],1);
                    oldval = p.num;
                }
            }
            queue.add(p);



            int [] res = new int[k];
            for(int i = 0 ; i < k ; i ++)
            {
                res[i] = queue.poll().num;
            }
            return res;
        }

}
